/**
 * 模拟实现树结构，使用孩子兄弟表示法
*/
#pragma once
#include <iostream>
#include <cassert>
namespace myTree
{
    const short CHILD = 1;
    const short BROTHER = 0;

    // 树的节点 （先描述）
    template <class T>
    struct Node
    {
    public:
        Node(const T& value = T())
            : _child(nullptr)
            , _brother(nullptr)
            , _value(value)
        {}

        Node(const Node<T>& another)
            : _child(another._child)
            , _brother(another._brother)
            , _value(another._value)
        {}

        const Node<T> operator=(const Node<T>& another)
        {
            if(this != &another)
            {
                _child = another._child;
                _brother = another._brother;
                _value = another._value;
            }
            return *this;
        }
        ~Node()
        {}

        Node<T>* _child;
        Node<T>* _brother;
        T _value;
    };


    // 树的结构（再组织）
    template <class T>
    class Tree
    {
        using node = Node<T>;
    public:
        Tree(const T& value = T())
            : _root(new node)
            , _size(1)
        {}
        void insert(node* pos, const T& value, short flag)
        {
            if(flag == CHILD)
                assert(flag == CHILD && pos->_child == nullptr);
            if(flag == BROTHER)
                assert(flag == BROTHER && pos->_brother == nullptr);

            //1. 创建一个树的节点
            node* newnode = new node(value);
            //2. 插入对应位置    
            flag == CHILD ? pos->_child = newnode : pos->_brother = newnode;
            // 3. 个数加一
            ++ _size;
        }
        void erase(node* pos)
        {
            // 需要递归删除
            if(pos->_child == nullptr && pos->_brother == nullptr)
            {
                delete pos;
                pos = nullptr;
                return;
            }
            if(pos == nullptr)
            {
                return;
            }

            erase(pos->_child);
            erase(pos->_brother);
        }

        int size() {return _size;}
        node* root() {return _root;}
    private:
        node* _root; // 根节点
        int _size; // 数的节点的个数
    };
}